|
In computational geometry, the largest empty rectangle problem, maximal empty rectangle problem or maximum empty rectangle problem, is the problem of finding a rectangle of maximal size to be placed among obstacles in the plane. There are a number of variants of the problem, depending on the particularities of this generic formulation, in particular, depending on the measure of the "size", domain (type of obstacles), and the orientation of the rectangle. The problems of this kind arise e.g., in electronic design automation, in design and verification of physical layout of integrated circuits.〔 describes algorithms for polygon operations involved in electronic design automation (design rule checking, circuit extraction, placement and routing).〕 A maximal empty rectangle (MER) is a rectangle which is not contained in another empty rectangle. Each side of a MER abuts an obstacle (otherwise the side may be shifted outwards, increasing the empty rectangle). An application of this kind is enumeration of "maximal white rectangles" in image segmentation R&D of image processing and pattern recognition. In the contexts of many algorithms for largest empty rectangles, "maximal empty rectangles" are candidate solutions to be considered by the algorithm, since it is easily proven that, e.g., a maximum-area empty rectangle is a maximal empty rectangle. ==Classification== In terms of size measure, the two most common cases are the largest-area empty rectangle and largest-perimeter empty rectangle. Another major classification is whether the rectangle is sought among axis-oriented or arbitrarily oriented rectangles. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Largest empty rectangle」の詳細全文を読む スポンサード リンク
|